import java.util.*;
public class Text {
    /*
    题目 1 : 数组的旋转: 把一个数组的最开始若干个元素移到数组末尾
    输入一个非递减排序的数组的一个旋转,输出该旋转数组的最小元素
    例如:数组{3,4,5,1,2} 为{1,2,3,4,5}的一个旋转,该数组最小值为1
    note:给出的所有元素都大于0 , 若数组大小为0,请返回0
     */
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(array[mid] > array[right]){
                left = mid + 1;
            }else if(array[mid] < array[right]){
                right = mid;
            }else{
                right--;
            }
        }
        return array[left];
    }

    /*
    题目 2 : 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     */
    //写成了: magazine 删掉一些字符能不能变成 ransomNote
    public static boolean canConstruct2(String ransomNote, String magazine) {
        int r = 0;
        int m = 0;
        while(r < ransomNote.length() &&  m < magazine.length()){
            if(ransomNote.charAt(r) == magazine.charAt(m)){
                r++;
                m++;
            }else{
                m++;
            }
        }
        return r == ransomNote.length() ;
    }

    //自己写的:
    //创建hashmap 的时间复杂度更高
     public boolean canConstruct1(String ransomNote, String magazine) {
         Map<Character,Integer> map = new HashMap<>();
         for(char x : magazine.toCharArray()){
             if(map.get(x) == null){
                 map.put(x,1);
             }else{
                 int val = map.get(x);
                 map.put(x,val + 1);
             }
         }
         int r = 0;
         while(r < ransomNote.length() && map.get(ransomNote.charAt(r)) != null && map.get(ransomNote.charAt(r)) > 0){
                 int val = map.get(ransomNote.charAt(r));
                 map.put(ransomNote.charAt(r),val - 1);
                 r++;
             }
             return r == ransomNote.length();
         }

         //官方结果:
         public static boolean canConstruct(String ransomNote, String magazine) {
             if(ransomNote.length() > magazine.length()){
                 return false;
             }
             int[] count = new int[26];
             for(char x : magazine.toCharArray()){
                 count[x - 97]++;
             }
             for(char x : ransomNote.toCharArray()){
                 if(count[x - 97] > 0){
                     count[x - 97]--;
                 }else{
                     return false;
                 }
             }
             return true;
         }

    public static void main(String[] args) {
        String r = "aab";
        String m = "baa";
        boolean ret = canConstruct(r, m);
        System.out.println(ret);
        r.toCharArray();
    }

    /*
    题目 3: 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
    注意：若s 和 t中每个字符出现的次数都相同，则称s 和 t互为字母异位词。
     */
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        //往后 --> s 和 t 的长度是一样的!!
        //不需要最后再去查看 count 数组有没有全部归0!
        int[] count = new int[26];
        for(char x : s.toCharArray()){
            count[x - 97]++;
        }
        for(char x : t.toCharArray()){
            if(count[x - 97] > 0){
                count[x - 97]--;
            }else{
                return false;
            }
        }
        return true;
    }

    /*
    题目 4 : 判断链表有没有环的!!
     */
    //思路:快慢指针!
    //快指针走两步,而慢指针走一步
    //在没有环的情况下,每一次移动,快慢指针之间的距离都会 +1 !
    //但如果有环,快指针先进入环,慢指针后进入环,两指针之间的距离先增大,后面随着 快指针再一次入环,两者距离每次移动减少 1 !!这样一定能相遇!!
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
     }
    }
    public boolean hasCycle1(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(slow != fast){
            if(fast == null || fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        Set<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while(cur != null){
            if(!set.contains(cur)){
                set.add(cur);
                cur = cur.next;
            }else{
                return true;
            }
        }
        return false;

    }

    /*
    题目5 : 合并两个有序链表,使其变成一个有序链表
     */
    //方法一: 利用一个哑节点,指针
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(0);
        ListNode temp = newHead;
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                temp.next = cur1;
                temp = cur1;
                cur1 = cur1.next;
            }else{
                temp.next = cur2;
                temp = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null){
            temp.next = cur1;
        }
        if(cur2 != null){
            temp.next = cur2;
        }
        return newHead.next;
    }
    //递归
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }

    /*
    题目 6 : 移除链表所有 val 元素
     */
    //由于是单链表的缘故,利用前后指针
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}
